Grokking Google Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Google Easy
Add Binary (easy)
Solution: Add Binary
Valid Mountain Array (easy)
Solution: Valid Mountain Array
Set Mismatch (easy)
Solution: Set Mismatch
Is Subsequence (easy)
Solution: Is Subsequence
Length of Last Word (easy)
Solution: Length of Last Word
Search Insert Position (easy)
Solution: Search Insert Position
Repeated Substring Pattern (easy)
Solution: Repeated Substring Pattern
Monotonic Array (easy)
Solution: Monotonic Array
Count Nodes Equal to Average of Subtree (easy)
Solution: Count Nodes Equal to Average of Subtree
Find the Difference (easy)
Solution: Find the Difference
How Many Numbers Are Smaller Than the Current Number (easy)
Solution: How Many Numbers Are Smaller Than the Current Number
Binary Tree Paths (easy)
Solution: Binary Tree Paths
Find the Difference of Two Arrays (easy)
Solution: Find the Difference of Two Arrays
Merge Strings Alternately (easy)
Solution: Merge Strings Alternately
Reverse a LinkedList (easy)
Solution: Reverse a LinkedList
Google Medium
Gray Code (medium)
Solution: Gray Code
2 Keys Keyboard (medium)
Solution: 2 Keys Keyboard
Arithmetic Slices (medium)
Solution: Arithmetic Slices
Unique Length-3 Palindromic Subsequences (medium)
Solution: Unique Length-3 Palindromic Subsequences
Minimum Difference Between Largest and Smallest Value in Three Moves (medium)
Solution: Minimum Difference Between Largest and Smallest Value in Three Moves
Letter Combinations of a Phone Number (medium)
Solution: Letter Combinations of a Phone Number
01 Matrix (medium)
Solution: 01 Matrix
Maximum Points You Can Obtain from Cards (medium)
Solution: Maximum Points You Can Obtain from Cards
Strobogrammatic Number II (medium)
Solution: Strobogrammatic Number II
Maximum Length of Semi-Decreasing Subarrays (medium)
Solution: Maximum Length of Semi-Decreasing Subarrays
Minimum Area Rectangle (medium)
Solution: Minimum Area Rectangle
Count Unreachable Pairs of Nodes in an Undirected Graph (medium)
Solution: Count Unreachable Pairs of Nodes in an Undirected Graph
Single Number II (medium)
Solution: Single Number II
4Sum II (medium)
Solution: 4Sum II
Furthest Building You Can Reach (medium)
Solution: Furthest Building You Can Reach
Minimizing Array After Replacing Pairs With Their Product (medium)
Solution: Minimizing Array After Replacing Pairs With Their Product
Fair Distribution of Cookies (medium)
Solution: Fair Distribution of Cookies
Find Leaves of Binary Tree (medium)
Solution: Find Leaves of Binary Tree
Rotate Image (medium)
Solution: Rotate Image
Combination Sum (medium)
Solution: Combination Sum
Implement Trie (Prefix Tree) (medium)
Solution: Implement Trie (Prefix Tree)
Number of Islands (medium)
Solution: Number of Islands
Edit Distance (medium)
Solution: Edit Distance
Container With Most Water (Medium)
Solution: Container With Most Water
Meeting Rooms II (medium)
Solution: Meeting Rooms II
Google Hard
Shortest Subarray with Sum at Least K (hard)
Solution: Shortest Subarray with Sum at Least K
Reverse Pairs (hard)
Solution: Reverse Pairs
Nth Magical Number (hard)
Solution: Nth Magical Number
Candy (hard)
Solution: Candy
Arithmetic Slices II - Subsequence (hard)
Solution: Arithmetic Slices II - Subsequence
Burst Balloons (hard)
Solution: Burst Balloons
Sum of Distances in Tree (hard)
Solution: Sum of Distances in Tree
Maximum Score of a Good Subarray (hard)
Solution: Maximum Score of a Good Subarray
Trapping Rain Water (hard)
Solution: Trapping Rain Water
First Missing Positive (hard)
Solution: First Missing Positive
Solution: Reverse Pairs

Problem Statement

Given an array of integers nums, return the count of reverse pairs in the array.

A reverse pairis a pair (i, j) where:

  • 0 <= i < j < nums.length and
  • nums[i] > 2 * nums[j].

Examples

  • Example 1:

    • Input: nums = [4, 3, 4, 1]
    • Expected Output: 3
    • Justification: The three reverse pairs are (0, 3), (1, 3) and (2, 3).
  • Example 2:

    • Input: nums = [4, 1, 2]
    • Expected Output: 1
    • Justification: There is only one reverse pair (0, 1) since 4 > 2 * 1.
  • Example 3:

    • Input: nums = [6,5,4,3,2,1]
    • Expected Output: 6
    • Justification: The siz reverse pairs are (0, 4), (0, 5),(1, 4), (1, 5), (2, 5) and (3, 5).

Solution

To solve this problem, we'll utilize a divide and conquer approach, similar to the merge sort algorithm. This method is effective because it allows us to efficiently compare elements and count reverse pairs during the merge process. As we divide the array into smaller subarrays, we can more manageably identify and count the pairs that meet our criteria before merging them back together. This technique not only helps in sorting the array but also enables us to count the reverse pairs without checking each pair explicitly, significantly reducing the time complexity.

The core idea revolves around dividing the array into two halves, counting the reverse pairs in each half recursively, and then counting the pairs that cross the midpoint during the merge phase. This approach works effectively because it systematically reduces the problem size while ensuring that all potential reverse pairs are counted. The merge step is crucial, as it allows us to count the reverse pairs across the divided parts efficiently, leveraging the sorted order of subarrays to make quicker comparisons.

Step-by-Step Algorithm

  1. Implement the recursive function reversePairsRec:

    • If the current subarray consists of one element or is invalid (left index greater than right), return 0 since no reverse pairs can be found.
    • Calculate the middle index of the current subarray.
    • Recursively call reversePairsRec for the left half of the array and add the result to the count.
    • Recursively call reversePairsRec for the right half of the array and add the result to the count.
    • Call mergeAndCount with the left, middle, and right indices of the current subarray, add this result to the total count, and return it.
  2. Count and merge with mergeAndCount:

    • Initialize a count of reverse pairs to 0.
    • Use two pointers: one starting at the left half's beginning and another at the right half's beginning.
    • For each element in the left subarray, iterate through the right subarray to find elements that satisfy the reverse pair condition (left element is more than twice the right element). For each such element found, add to the count the number of remaining elements in the left subarray, as they all will form reverse pairs with the current element in the right subarray.
    • Sort the current subarray to ensure the merging process works correctly for future recursive calls.
    • Return the count of reverse pairs found in this step.
  3. Return Final Count:

    • Return the count of reverse pairs at the end.

Algorithm Walkthrough

Let's consider the Input: nums = [6,5,4,3,2,1]

Initial Setup

  • We start with the array [6,5,4,3,2,1] and the goal to count the reverse pairs.
  • The initial call is reversePairs([6,5,4,3,2,1]), which translates to reversePairsRec([6,5,4,3,2,1], 0, 5).

First Division

  • Divide: The array is split into two halves at the midpoint index 2, resulting in two subarrays: [6,5,4] (left) and [3,2,1] (right).

Left Half: [6,5,4]

  • Divide Left Half: Further split [6,5,4] into [6, 5] (left) and [4] (right).

    • [4] is a base case, returns 0 reverse pairs.

    • Left Subarray [6,5]:

      • Split into [6] and [5].
      • Both [6] and [5] are base cases, return 0 reverse pairs each.
      • Merge [6] and [5]:
        • mergeAndCount finds 0 reverse pair because 6 < 2*5.
        • After merging, the subarray becomes [5, 6].
    • Right Subarray [4]: [4] is a base case, returns 0 reverse pairs.

    • Merge [6, 5] with [4]:

      • No new reverse pairs found during this merge since 6 and 5 is not more than twice 4.
      • The merged subarray remains [4,5,6].

Right Half: [3,2,1]

  • Divide Right Half: Split [3,2,1] into [3, 2] (left) and [1] (right).

    • Left Subarray [3, 2]:

      • Split into [3] and [2].

      • Both [3] and [2] are base cases, return 0 reverse pairs each.

      • Merge [3] and [2]:

        • mergeAndCount finds 0 reverse pair because 3 < 2*2.
        • After merging, the subarray becomes [2, 3].
      • Left Subarray [1]: [1] is a base case, returns 0 reverse pairs.

    • Merge [2,3] with [1]:

      • mergeAndCount finds 1 reverse pairs: 3 > 2*1. Now, reversePairs = 1.
      • The merged subarray becomes [1,2,3].

Final Merge: [4,5,6] with [1,2,3]

  • Merge Process:
    • At this stage, both halves [4,5,6] and [1,2,3] are individually sorted.
    • During the final merge, mergeAndCount operates on these two halves:
      • For [4] from the left subarray, it finds 1 reverse pairs with [1]. Now, reversePairs = reversePairs + 1 = 1 + 1 = 2.
      • For [5], it finds 2 reverse pairs with [1, 2]. Now, reversePairs = reversePairs + 2 = 2 + 2 = 4.
      • For [6], it also finds 2 reverse pairs with [1, 2]. Now, reversePairs = reversePairs + 2 = 4 + 2 = 6.
  • Final State:
    • After the merge, the entire array is sorted as [1,2,3,4,5,6], but most importantly, all reverse pairs have been counted throughout the divide and merge process. The total count of reverse pairs are 6.

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

Time Complexity

The time complexity of the algorithm is , where (n) is the length of the input array. This complexity arises because the algorithm employs a divide-and-conquer strategy, akin to merge sort. Here's the breakdown:

  • Dividing the array: The array is recursively divided into two halves until each subarray contains a single element, which takes time considering the depth of the recursion tree.
  • Counting and merging: During each merge step, the algorithm counts the reverse pairs and then sorts the merged parts. The counting of reverse pairs is done in linear time relative to the size of the subarrays being merged, and sorting is , where (k) is the number of elements in the subarray. Since the merge happens at every level of the recursion, and considering all levels, it sums up to .

Space Complexity

The space complexity of the solution is , primarily due to the temporary arrays used for sorting subsections of the original array during the merge process. Additionally, the recursive approach incurs a call stack depth of , but the dominant factor remains the space needed for sorting, leading to the overall space complexity.

Reverse Pairs (hard)
Nth Magical Number (hard)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity